#include <vector>
#include <stack>
using namespace std;
class Solution {
public:
    int maximalRectangle(vector<vector<char> > &matrix) {
        int n=matrix.size();
        if (n==0) return 0;
        int m=matrix[0].size();
        if (m==0) return 0;
        int ans=0;
        vector<int> sum(m+1,0);
        for (int i=0;i<n;i++) {
            for (int j=0;j<m;j++)
                if (matrix[i][j]=='0') sum[j]=0; else ++sum[j];
            stack<pair<int, int> > s;
            for (int j=0;j<=m;j++) {
                int position=j;
                while (!s.empty() && s.top().first>=sum[j]) {
                    position=s.top().second;
                    if (ans<(j-s.top().second)*s.top().first) ans=(j-s.top().second)*s.top().first;
                    s.pop();
                }
                s.push(make_pair(sum[j], position));
            }
        }
        return ans;
    }
};
